/*
https://leetcode-cn.com/problems/escape-a-large-maze/solution/tao-chi-da-mi-gong-by-leetcode-solution-qxhz/
 */
import java.util.*;

public class Solution1036 {

    int[] dx=new int[]{0,1,0,-1};
    int[] dy=new int[]{1,0,-1,0};

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        Set<List<Integer>> set=new HashSet<>();
        for (int[] ints : blocked) {
            List<Integer> l=new ArrayList<>();
            l.add(ints[0]);
            l.add(ints[1]);
            set.add(l);
        }
        Queue<List<Integer>> queue=new LinkedList<>();
        List<Integer> s=new ArrayList<>();
        s.add(source[0]);
        s.add(source[1]);
        queue.add(s);
        Set<List<Integer>> set1=new HashSet<>();
        set1.add(s);
        int count=0;
        while (!queue.isEmpty()){
            if (count>blocked.length*(blocked.length-1)/2){
                break;
            }
            List<Integer> list=queue.poll();
            int x=list.get(0);
            int y=list.get(1);
            for (int i=0;i<4;i++){
                int xx=x+dx[i];
                int yy=y+dy[i];
                List<Integer> t=new ArrayList<>();
                t.add(xx);
                t.add(yy);
                if (xx>=0 && xx<1000000 && yy>=0 && yy<1000000 && !set.contains(t) && !set1.contains(t)){
                    count++;
                    queue.offer(t);
                    set1.add(t);
                    if (xx==target[0] && yy==target[1]){
                        return true;
                    }
                }
            }
        }
        if (count<=blocked.length*(blocked.length-1)/2){
            return false;
        }
        queue.clear();
        s=new ArrayList<>();
        s.add(target[0]);
        s.add(target[1]);
        queue.add(s);
        set1.clear();
        set1.add(s);
        count=0;
        while (!queue.isEmpty()){
            if (count>blocked.length*(blocked.length-1)/2){
                break;
            }
            List<Integer> list=queue.poll();
            int x=list.get(0);
            int y=list.get(1);
            for (int i=0;i<4;i++){
                int xx=x+dx[i];
                int yy=y+dy[i];
                List<Integer> t=new ArrayList<>();
                t.add(xx);
                t.add(yy);
                if (xx>=0 && xx<1000000 && yy>=0 && yy<1000000 && !set.contains(t) && !set1.contains(t)){
                    count++;
                    queue.offer(t);
                    set1.add(t);
                    if (xx==source[0] && yy==source[1]){
                        return true;
                    }
                }
            }
        }
        if (count<=blocked.length*(blocked.length-1)/2){
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1036().isEscapePossible(new int[][]{{0,3},{1,0},{1,1},{1,2},{1,3}},new int[]{0,0},new int[]{0,2}));
    }
}
